package d2;
import java.util.*;

public class Day14 {
    public static void main(String[] args) {

    }
    //课程表--拓扑排序
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = numCourses;
        int[] in = new int[n];//统计入度
        //1.建立领接矩阵
        Map<Integer,List<Integer>> edges =new HashMap<>();
        for(int i=0;i<prerequisites.length;i++) {
            int a = prerequisites[i][0],b=prerequisites[i][1];//b-->a
            if(!edges.containsKey(b)) edges.put(b,new ArrayList<>());
            edges.get(b).add(a);
            in[a]++;
        }
        //2.建图，把入队为0的点的下标加入队列
        Queue<Integer> q = new LinkedList<>();
        for(int i=0;i<n;i++)
            if(in[i]==0) q.add(i);

        //3.进行拓扑排序
        while (!q.isEmpty()) {
            int t = q.poll();
            //把t连接的边去掉
            for(int x:edges.getOrDefault(t,new ArrayList<>())) {
                in[x]--;
                if(in[x]==0) q.add(x);
            }
        }
        //4.统计结果
        for(int x:in) {
            if(x!=0) return false;
        }
        return true;
    }
}
